package Graph;

import java.util.*;

public class 蓝桥王国2 {

    static class Node {
        public Node(int val) {
            dist = Long.MAX_VALUE;
            bian = new ArrayList<>();
            this.val = val;
        }

        int val;
        Node pre; //上一个节点
        long dist;
        boolean isVisited = false;
        List<Edge> bian;
    }

    static class Edge { //边
        Node next;  //这条边指向的节点
        long weight; //权值

        public Edge(Node next, long weight) {
            this.next = next;
            this.weight = weight;
        }
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        Node[] nodes = new Node[N + 1];

        for (int i = 1; i <= N; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 1; i <= M; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            long w = scanner.nextInt();
            nodes[u].bian.add(new Edge(nodes[v], w));
        }
        djs(nodes, nodes[1]);

        for (int i = 1; i <= N; i++) {
            if (nodes[i].dist != Long.MAX_VALUE) {
                System.out.print(nodes[i].dist + " ");
            } else {
                System.out.print(-1 + " ");
            }
        }
    }

    private static void djs(Node[] nodes, Node start) {
        start.dist = 0;
        //优先队列
        PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>(Comparator.comparingLong(value -> value.dist));
        priorityQueue.offer(start);

        while (!priorityQueue.isEmpty()) {
            Node poll = priorityQueue.poll();
            poll.isVisited = true;
            for (Edge edge : poll.bian) {
                if (!edge.next.isVisited) {//没有被访问
                    long d = poll.dist + edge.weight;
                    if (d < edge.next.dist) {
                        edge.next.dist = d;
                        priorityQueue.offer(edge.next);
                    }
                }
            }
        }
    }

    public static void print(Integer[][] dist) {
        for (Integer[] integers : dist) {
            System.out.println(Arrays.toString(integers));
        }

    }
}
